package leetcode_acm.leetcode_1;

import sun.reflect.generics.tree.Tree;

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

/**
 * 功能描述
 *
 * @author: 张庭杰
 * @date: 2023年03月07日 20:19
 */
public class MaxDepth {
    static class TreeNode{
        int val;
        TreeNode left;
        TreeNode right;
        public TreeNode(int val){
            this.val = val;
            this.left = null;
            this.right = null;
        }
        public TreeNode(int val,TreeNode left,TreeNode right){
            this.val = val;
            this.left =left;
            this.right = right;
        }
    }

    static class Solution{
        public static TreeNode buildTree(){
            //层次建树
            Scanner in = new Scanner(System.in);
            //1. 读取数组中有多少个元素
            int n = in.nextInt();
            //2. 读取数组
            int[] nums = new int[n];
            for(int i = 0;i<n;i++){
                nums[i] = in.nextInt();
            }
            //3. 建树
            if(nums.length == 0){
                return null;
            }
            //层次遍历
            Queue<TreeNode> q = new LinkedList<>();
            TreeNode root = new TreeNode(nums[0]);
            q.offer(root);
            for(int i = 1;i<nums.length;){
                TreeNode head = q.poll();
                int leftNum = nums[i++];
                if(leftNum!=-1) {
                    head.left = new TreeNode(leftNum);
                    q.offer(head.left);
                }
                int rightNum = nums[i++];
                if(rightNum != -1){
                    head.right = new TreeNode(rightNum);
                    q.offer(head.right);
                }
            }
            return root;
        }

        static int maxDepth(TreeNode root){
            if(root == null){
                return 0;
            }
            int leftMax = maxDepth(root.left);
            int rightMax = maxDepth(root.right);
            return Math.max(leftMax,rightMax)+1;
        }
    }

    public static void main(String[] args) {
        TreeNode root = Solution.buildTree();
        System.out.println(Solution.maxDepth(root));
    }
}
